|
|
Výpočetní složitost v teorii grafů
Melka, Jakub ; Kratochvíl, Jan (vedoucí práce) ; Fiala, Jiří (oponent)
V předložené práci studujeme problém rekonstrukce grafu ze seznamu uzavřených okolí vrcholů tohoto grafu. Tento problém, původně zformulovaný V. Sósovou, budeme zkoumat z hlediska teorie parametrizované složitosti a zobecníme jej na problém rekonstruovatelnosti vzhledem ke třídám grafů. V této práci dokážeme, že tento problém leží ve třídě složitosti FPT vzhledem k parametru omezené stromové šířky a omezeného maximálního stupně nebo ke 2-degenerovaných grafům s omezeným počtem jistých indukovaných podgrafů, kde parametr je počet těchto podgrafů. Dále dokážeme, že problém rekonstruovatelnosti vzhledem ke třídě grafů s omezeným vrcholovým pokrytím leží ve třídě složitosti XP. Na závěr dokážeme vzájemnou nezávislost získaných výsledků.
|
|
|
Graph data analysis using deep learning methods
Vancák, Vladislav ; Svoboda, Martin (vedoucí práce) ; Majerech, Vladan (oponent)
Cílem této práce je prozkoumat existující metody pro vytváření grafových embeddingů. Chceme reprezentovat vrcholy neorientovaných vážených grafů pomocí vektorů malé dimenze, taktéž označovaných jako embeddingy, a to za účelem vytvoření vhodné reprezentace pro použití v různých analyt- ických úlohách jako clustering nebo predikce hran. Nejprve představíme několik současných přístupů pro vytváření takových embeddingů. Následně navrhneme několik úprav a vylepšení a ukážeme jejich přínosy. Nakonec vytvoříme sadu metrik pro vyhodnocení výkonnosti modelů a použijeme je k experimentálnímu vyhodnocení a vzájemnému porovnání prezentovaných algoritmů na sérii úloh jako vizualizace a rekonstrukce grafů. 1
|
|
|
Výpočetní složitost v teorii grafů
Melka, Jakub ; Kratochvíl, Jan (vedoucí práce) ; Fiala, Jiří (oponent)
V předložené práci studujeme problém rekonstrukce grafu ze seznamu uzavřených okolí vrcholů tohoto grafu. Tento problém, původně zformulovaný V. Sósovou, budeme zkoumat z hlediska teorie parametrizované složitosti a zobecníme jej na problém rekonstruovatelnosti vzhledem ke třídám grafů. V této práci dokážeme, že tento problém leží ve třídě složitosti FPT vzhledem k parametru omezené stromové šířky a omezeného maximálního stupně nebo ke 2-degenerovaných grafům s omezeným počtem jistých indukovaných podgrafů, kde parametr je počet těchto podgrafů. Dále dokážeme, že problém rekonstruovatelnosti vzhledem ke třídě grafů s omezeným vrcholovým pokrytím leží ve třídě složitosti XP. Na závěr dokážeme vzájemnou nezávislost získaných výsledků.
|
host ::
RSS.